class Solution {
    /**
        经典案例:[2,3,1]
        
        为什么一定要从右边开始? 基准数在左边，如果先从左边开始，无法保证之后从右边开始的数是小于等于target的
        如 [2 1 4 5] 先从左边开始，left定位到4的位置，而right只能移动到left的位置，没办法移动到1的位置
    */
    public int[] sortArray(int[] nums) {
        quickSort(nums, 0, nums.length - 1);
        return nums;
    }
    public void quickSort(int[] nums, int left, int right){
        if(left>=right)
            return;
        int ll = left, rr = right;
        int flag = nums[left];
        while( ll<rr ){
            while( ll<rr && nums[rr]>=flag )
                rr--;
            while( ll<rr && nums[ll]<=flag )
                ll++;
            if( ll<rr ){
                int tmp = nums[ll];
                nums[ll] = nums[rr];
                nums[rr] = tmp;
            }
        }
        nums[left] = nums[rr];
        nums[rr] = flag;
        quickSort(nums,left,rr-1);
        quickSort(nums,rr+1,right);
    }
}